#include "Expand.h"
#include <assert.h>
#include <iostream>

namespace SymCe{
	Multitree * expand_power(Multitree * base, Integer exponent);
	//the function is basically same as all other functions. Call it on subtrees and then do something with the current node.
	//It would be better probably to have it once. But how to do it?
	Multitree * expand_tree(Multitree * tree){
		//If current symbol is not MULTIPLY, then just recursively expand subtrees and return it.
		//Otherwise do something
		//We can of course use one if - is it MULTIPLY or not? But I decided to use switch again
		//because i know how many childs the node has and do not need to use many ifs (for adding
		//child to the end of linked list - first node must be handled differently)
		Multitree * to_return = NULL;
		ListOfChilds * add_to = NULL;
		ListOfChilds * pass = NULL;
		Multitree * tmp = NULL;
		switch (tree->symbol.type){
			case NUMBER:
			case VARIABLE:
			case CONSTANT:
				//No childs. Just copy it.
				return copy_tree(tree);
				break;
			case FUNCTION:
				//We call expand_tree() to argument and attach it here.
				to_return = new Multitree;
				to_return->symbol = tree->symbol;
				to_return->childs = new ListOfChilds;
				to_return->childs->next = NULL;
				to_return->childs->inverted = false;
				to_return->childs->subtree = expand_tree(tree->childs->subtree);
				return to_return;
				break;
			case OPERATOR:
				to_return  = new Multitree;
				to_return->symbol = tree->symbol;
				//Add there first child
				to_return->childs = new ListOfChilds;
				to_return->childs->inverted = tree->childs->inverted;
				to_return->childs->next = NULL;
				to_return->childs->subtree = expand_tree(tree->childs->subtree);
				//Add other childs
				add_to = to_return->childs;
				pass = tree->childs->next;
				while (pass != NULL){
					add_to->next = new ListOfChilds;
					add_to->next->inverted = pass->inverted;
					add_to->next->next = NULL;
					add_to->next->subtree = expand_tree(pass->subtree);
					add_to = add_to->next;
					pass = pass->next;
				}

				if (tree->symbol.oper == POWER){
					Multitree * exponent = to_return->childs->next->subtree;
					//if exponent is whole number
					if (exponent->symbol.type == NUMBER){
						if (exponent->symbol.number.is_int()){
							//we know, that it is something raised to integer. If it is not 1, -1 or 0 then we should expand it
							//we expand a^3 to a*a*a and then call expand_multiply to it.
							//I could write one if with logical 'and', but I think this is more readable
							//We can do this, since we know, that it is an integer.
							double dou_power = exponent->symbol.number.get_double();
							bool inverted = (dou_power < 0);
							Integer int_power;
							if (inverted){
								int_power = static_cast<Integer> (-dou_power);
							}else{
								int_power = static_cast<Integer> (dou_power);
							}
							if (int_power > 1){
								//now we do something
								Multitree * base = copy_tree(to_return->childs->subtree);
								//we have base in base and exponent in int_power. We can delete to_return.
								delete_tree(to_return);
								to_return = expand_power(base, int_power);
								/*
								to_return = new Multitree;
								to_return->symbol.type = OPERATOR;
								to_return->symbol.oper = MULTIPLY;
								to_return->childs = NULL;
								//attach them to to_return
								for (Integer i = 0; i < int_power; ++i){
									pass = new ListOfChilds;
									pass->inverted = inverted;
									pass->subtree = copy_tree(base);
									pass->next = to_return->childs;
									to_return->childs = pass;
								}
								*/
								if (inverted){
									tmp = give_me_tree_with_two_childs();
									delete tmp->childs->subtree;
									tmp->childs->subtree = to_return;
									tmp->childs->next->subtree->symbol.type = NUMBER;
									tmp->childs->next->subtree->symbol.number = -1;
									tmp->childs->next->inverted = false;
									tmp->childs->inverted = false;
									tmp->symbol.type = OPERATOR;
									tmp->symbol.oper = POWER;
									to_return = tmp;
								}

								//clean up base
								delete_tree(base);
							} //|exp| > 1
						}//is int
					}//is number
				}//is power

				//And now, if the symbol is multiply (either it was multiply or it is now, because of expansion of power)
				//we expand it. If it is not multiply, then we just return to_return
				//And we should somehow put the tree to "canonical form" before returning it.
				if (to_return->symbol.oper == MULTIPLY){
					tmp = to_return;
					to_return = expand_multiply(tmp);
					delete_tree(tmp);

				}
				
				rehang_tree(to_return);
				sort_tree(to_return);
				return to_return;
				break;
		}
		assert(false);
		return NULL;
	}

	Multitree * expand_multiply(Multitree * tree){
		//Separate the childs.
		ListOfChilds * upper_plus = NULL; //Not inverted with plus in subtree.
		ListOfChilds * upper_normal = NULL; //Not inverted without plus in subtree
		ListOfChilds * lower_plus = NULL; //Inverted with plus in subtree
		ListOfChilds * lower_normal = NULL; //inverted without plus in subtree
		ListOfChilds * pass = tree->childs;
		ListOfChilds * added;
		while (pass != NULL){
			added = new ListOfChilds;
			added->subtree = copy_tree(pass->subtree);
			added->inverted = pass->inverted; //It might not be necessary, but it makes things easier.
			if (pass->inverted){
				if ((pass->subtree->symbol.type == OPERATOR) && (pass->subtree->symbol.oper == PLUS)){
					added->next = lower_plus;
					lower_plus = added;
				}else{
					added->next = lower_normal;
					lower_normal = added;
				}
			}else{
				if ((pass->subtree->symbol.type == OPERATOR) && (pass->subtree->symbol.oper == PLUS)){
					added->next = upper_plus;
					upper_plus = added;
				}else{
					added->next = upper_normal;
					upper_normal = added;
				}
			}
			pass = pass->next;
		}
		//We have them separated to boxes.
		//Now what?
		//We create (0+(*)) node, where * will be those that are "normal"
		//means: from a*(b+c)*d we create (0+a*d)*(b+c). Then we can work with it consistently
		//We put it then to upper_plus and we can forget about upper_normal.
		if(upper_normal != NULL){
			added = new ListOfChilds;
			added->inverted = false; //upper
			added->subtree = new Multitree; //plus
			added->subtree->symbol.type = OPERATOR;
			added->subtree->symbol.oper = PLUS;
			added->subtree->childs = new ListOfChilds;
			//added->subtree->childs->next is defined later
			
			//first child should be 0
			Multitree * zero = new Multitree;
			zero->childs = NULL;
			zero->symbol.type = NUMBER;
			zero->symbol.number = Number(0);
			added->subtree->childs->inverted = false;
			added->subtree->childs->subtree = zero;
			if(upper_normal->next == NULL){
				//Second should be either * or upper normal. Childs of * should be upper_normal
				added->subtree->childs->next = upper_normal;
				assert(added->subtree->childs->next->next == NULL);
			}else{
				added->subtree->childs->next = new ListOfChilds;
				added->subtree->childs->next->next = NULL;
				added->subtree->childs->next->inverted = false;
				added->subtree->childs->next->subtree = new Multitree; //Multiply.
				added->subtree->childs->next->subtree->symbol.type = OPERATOR;
				added->subtree->childs->next->subtree->symbol.oper = MULTIPLY;
				added->subtree->childs->next->subtree->childs = upper_normal;
			}
			added->next = upper_plus;

			upper_plus = added;
		}
		upper_normal = NULL;


		//same for lower.
		//I know, that it is not very good to copy the code, but it seems as fastest way to write it.
		//TODO - some code reuse
		if(lower_normal != NULL){

			//first child should be 0
			Multitree * zero = new Multitree;
			zero->childs = NULL;
			zero->symbol.type = NUMBER;
			zero->symbol.number = Number(0);

			added = new ListOfChilds;
			added->inverted = true; //lower
			added->subtree = new Multitree; //plus
			added->subtree->symbol.type = OPERATOR;
			added->subtree->symbol.oper = PLUS;
			added->subtree->childs = new ListOfChilds;
			//added->subtree->childs->next is defined later
			added->subtree->childs->inverted = false;
			added->subtree->childs->subtree = zero;

			if(lower_normal->next == NULL){
				//Second should be either * or lower normal. Childs of * should be lower_normal
				added->subtree->childs->next = lower_normal;
				added->subtree->childs->next->inverted = false;
				assert(added->subtree->childs->next->next == NULL);
			}else{
				added->subtree->childs->next = new ListOfChilds;
				added->subtree->childs->next->next = NULL;
				added->subtree->childs->next->inverted = false;
				added->subtree->childs->next->subtree = new Multitree; //Multiply.
				added->subtree->childs->next->subtree->symbol.type = OPERATOR;
				added->subtree->childs->next->subtree->symbol.oper = MULTIPLY;
				added->subtree->childs->next->subtree->childs = lower_normal;
			}
			added->next = lower_plus;

			lower_plus = added;
		}




		if (upper_plus != NULL){
			//If there is any with plus, then do something until there is only one.
			while (upper_plus->next != NULL){
				//Take the first two, multiply each child with each subchild and put it back.
				ListOfChilds * first_child = upper_plus;
				ListOfChilds * second_child = first_child->next;
				upper_plus = second_child->next;
				//Now we need to go through "sons"
						
				//Create one simple multiply tree.
				Multitree * multiplied = new Multitree;
				multiplied->symbol.type = OPERATOR;
				multiplied->symbol.oper = MULTIPLY;
				multiplied->childs = new ListOfChilds;
				multiplied->childs->inverted = false;
				multiplied->childs->subtree = NULL;
				multiplied->childs->next = new ListOfChilds;
				multiplied->childs->next->inverted = false;
				multiplied->childs->next->next = NULL;
				multiplied->childs->next->subtree = NULL;

				ListOfChilds * newlist = NULL;

				ListOfChilds * pass1 = first_child->subtree->childs;
				ListOfChilds * pass2 = NULL;
				while (pass1 != NULL){
					pass2 = second_child->subtree->childs;
					while(pass2 != NULL){
						//We take one child from the first plus, one from the second, we combine them (using multiplied tree)
						//And attach them to the newlist.
						added = new ListOfChilds;
						//Set sign
						added->inverted = (pass1->inverted ^ pass2->inverted); //XOR
						//Attach multiplication to 
						added->subtree = copy_tree(multiplied);
						added->subtree->childs->subtree = copy_tree(pass1->subtree);
						added->subtree->childs->next->subtree = copy_tree(pass2->subtree); //Tree must be copied.
						rehang_tree(added->subtree);
						added->next = newlist;
						newlist = added;
						pass2 = pass2->next;
					}
					pass1=pass1->next;
				}
				//We have new list of childs for our first tree.
				//Now we delete childs and create a new one that will be attached to the tree.
				delete_tree(first_child->subtree);
				delete_tree(second_child->subtree);
				delete second_child;
				first_child->subtree = new Multitree;
				first_child->subtree->symbol.type = OPERATOR;
				first_child->subtree->symbol.oper = PLUS;
				first_child->inverted = false; //This is, because it is UPPER!
				first_child->subtree->childs = newlist;
				//Now we can attach it back to the list.
				first_child->next = upper_plus;
				upper_plus = first_child;
			}
		}

		//copy paste for lower_plus

		if (lower_plus != NULL){
			//If there is any with plus, then do something until there is only one.
			while (lower_plus->next != NULL){
				//Take the first two, multiply each child with each subchild and put it back.
				ListOfChilds * first_child = lower_plus;
				ListOfChilds * second_child = first_child->next;
				lower_plus = second_child->next;
				//Now we need to go through "sons"
						
				//Create one simple multiply tree.
				Multitree * multiplied = new Multitree;
				multiplied->symbol.type = OPERATOR;
				multiplied->symbol.oper = MULTIPLY;
				multiplied->childs = new ListOfChilds;
				multiplied->childs->inverted = false;
				multiplied->childs->subtree = NULL;
				multiplied->childs->next = new ListOfChilds;
				multiplied->childs->next->inverted = false;
				multiplied->childs->next->next = NULL;
				multiplied->childs->next->subtree = NULL;

				ListOfChilds * newlist = NULL;

				ListOfChilds * pass1 = first_child->subtree->childs;
				ListOfChilds * pass2 = NULL;
				while (pass1 != NULL){
					pass2 = second_child->subtree->childs;
					while(pass2 != NULL){
						//We take one child from the first plus, one from the second, we combine them (using multiplied tree)
						//And attach them to the newlist.
						added = new ListOfChilds;
						//Set sign
						added->inverted = (pass1->inverted ^ pass2->inverted); //XOR
						//Attach multiplication to 
						added->subtree = copy_tree(multiplied);
						added->subtree->childs->subtree = copy_tree(pass1->subtree);
						added->subtree->childs->next->subtree = copy_tree(pass2->subtree);
						rehang_tree(added->subtree);
						added->next = newlist;
						newlist = added;
						pass2 = pass2->next;
					}
					pass1=pass1->next;
				}
				//We have new list of childs for our first tree.
				//Now we delete childs and create a new one that will be attached to the tree.
				delete_tree(first_child->subtree);
				delete_tree(second_child->subtree);
				delete second_child;
				first_child->subtree = new Multitree;
				first_child->subtree->symbol.type = OPERATOR;
				first_child->subtree->symbol.oper = PLUS;
				first_child->inverted = true; //This is, because it is LOWER!
				first_child->subtree->childs = newlist;
				//Now we can attach it back to the list.
				first_child->next = lower_plus;
				lower_plus = first_child;
			}
		}

		//Now we have upper_plus and upper_minus as we want them.
		Multitree * to_return;
		if (lower_plus == NULL){
			to_return = upper_plus->subtree;
			delete upper_plus;
			return to_return;
		}

		to_return = new Multitree;
		to_return->symbol.type = OPERATOR;
		to_return->symbol.oper = MULTIPLY;
		if (upper_plus == NULL){
			//create 1/lower_plus
			to_return->childs = new ListOfChilds;
			to_return->childs->inverted = false;
			to_return->childs->subtree = new Multitree;
			to_return->childs->subtree->childs = NULL;
			to_return->childs->subtree->symbol.type = NUMBER;
			to_return->childs->subtree->symbol.number = Number(1);
			to_return->childs->next = lower_plus;
		}else{
			to_return->childs = upper_plus;
			to_return->childs->next = lower_plus;
		}
		return to_return;
	}

	Multitree * expand_power(Multitree * base, Integer exponent){
		//creates (a^n + a^(n-1)*b + ... + b^n) from (a+b)^n
		//does not use binomial theorem, because it has to work also for (a+b+c+...)^n
		//we make squares of the base until we are over the exponent and then we delete
		//those we do not need and multiply rest.
		//example: (a+b)^5
		//we create (a+b)^1 = (a+b)
		//(a+b)^2 = (a^2+b^2+2*a*b)
		//(a+b)^4 = (a^2+b^2+2*a*b)^2 = .....
		//delete (a+b) ^2
		//multiply (a+b)^1 * (a+b)^4
		Multitree * to_return = NULL;
		Integer counter = 2;
		assert(exponent > 1);
		ListOfChilds * squares=NULL;
		squares = new ListOfChilds;
		squares->next = NULL;
		squares->subtree =copy_tree(base);
		squares->inverted = false;
		Multitree * added = NULL;
		Multitree * tmp = NULL;
		ListOfChilds * tmpchilds = NULL;

		while(counter < exponent){
			//we take previous node, create multiply with two copies of it and expand them
			added = new Multitree;
			added->symbol.type = OPERATOR;
			added->symbol.oper = MULTIPLY;
			added->childs = new ListOfChilds;
			added->childs->next = new ListOfChilds;
			added->childs->next->next = NULL;
			added->childs->next->inverted = false;
			added->childs->next->subtree = copy_tree(squares->subtree);
			added->childs->inverted = false;
			added->childs->subtree = copy_tree(squares->subtree);
			//added is previous * previous
			tmp = expand_multiply(added);
			//some of these might redundand - so be it
			//TODO: create "function" canonicalize_tree() that does this stuff for me
			delete_tree(added);
			added = canonicalize_tree(tmp);
			delete_tree(tmp);
			counter = counter * 2;
			//now we add added to squares
			tmpchilds = new ListOfChilds;
			tmpchilds->inverted = false;
			tmpchilds->subtree = added;
			tmpchilds->next = squares;
			squares = tmpchilds;
		}
		ListOfChilds * to_multiply = NULL;
		//now we should have some powers of base in squares
		//counter is now two times the biggest power of two in the list (and greater than exponent)
		counter = counter /2;
		//now we go through the squares and delete those we do not need (and move those we need to another list)
		while (exponent !=0){
			assert(squares != NULL);
			tmpchilds = squares;
			squares = squares->next;
			if(counter > exponent){
				//we do not need the current power
				delete_tree(tmpchilds->subtree);
				delete tmpchilds;
			}else{
				//we need that power
				tmpchilds->next = to_multiply;
				to_multiply = tmpchilds;
				exponent = exponent-counter;
			}
			counter = counter/2;
		}
		while(counter > 0){
			tmpchilds = squares;
			squares = squares->next;
			delete_tree(tmpchilds->subtree);
			delete tmpchilds;
			counter = counter / 2;
		}
		//now we should have correct powers in to_multiply list. We put it to some multiply tree and pass it to expand_multiply
		tmp = new Multitree;
		tmp->symbol.type = OPERATOR;
		tmp->symbol.oper = MULTIPLY;
		tmp->childs = to_multiply;
		to_return = expand_multiply(tmp);
		delete_tree(tmp);
		return to_return;
	}

}
